|
In computer science, the complexity function of a string, a finite or infinite sequence of letters from some alphabet, is the function that counts the number of distinct factors (substrings of consecutive symbols) from that string. More generally, the complexity function of a language, a set of finite words over an alphabet, counts the number of distinct words of given length. ==Complexity function of a word== Let ''u'' be a (possibly infinite) sequence of symbols from an alphabet. Define the function ''p''''u''(''n'') of a positive integer ''n'' to be the number of different factors (consecutive substrings) of length ''n'' from the string ''u''.〔Lothaire (2011) p.7〕〔〔Pytheas Fogg (2002) p.3〕〔Berstel et al (2009) p.82〕〔Allouche & Shallit (2003) p.298〕 For a string ''u'' of length at least ''n'' over an alphabet of size ''k'' we clearly have : the bounds being achieved by the constant word and a disjunctive word,〔Bugeaud (2012) p.91〕 for example, the Champernowne word respectively.〔Cassaigne & Nicolas (2010) p.165〕 For infinite words ''u'', we have ''p''''u''(''n'') bounded if ''u'' is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle). Conversely, if ''p''''u''(''n'') ≤ ''n'' for some ''n'', then ''u'' is ultimately periodic.〔〔Allouche & Shallit (2003) p.302〕 An aperiodic sequence is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function (this is the Morse–Hedlund theorem),〔〔Cassaigne & Nicolas (2010) p.166〕 so ''p''(''n'') is at least ''n''+1.〔Lothaire (2011) p.22〕 A set ''S'' of finite binary words is ''balanced'' if for each ''n'' the subset ''S''''n'' of words of length ''n'' has the property that the Hamming weight of the words in ''S''''n'' takes at most two distinct values. A balanced sequence is one for which the set of factors is balanced.〔Allouche & Shallit (2003) p.313〕 A balanced sequence has complexity function at most ''n''+1.〔Lothaire (2011) p.48〕 A Sturmian word over a binary alphabet is one with complexity function ''n'' + 1.〔Pytheas Fogg (2002) p.6〕 A sequence is Sturmian if and only if it is balanced and aperiodic.〔Lothaire (2011) p.46〕〔Allouche & Shallit (2003) p.318〕 An example is the Fibonacci word.〔 More generally, a Sturmian word over an alphabet of size ''k'' is one with complexity ''n''+''k''−1. An Arnoux-Rauzy word over a ternary alphabet has complexity 2''n'' + 1:〔 an example is the Tribonacci word.〔Pytheas Fogg (2002) p.368〕 For recurrent words, those in which each factor appears infinitely often, the complexity function almost characterises the set of factors: if ''s'' is a recurrent word with the same complexity function as ''t'' are then ''s'' has the same set of factors as ''t'' or δ''t'' where δ denotes the letter doubling morphism ''a'' → ''aa''.〔Berstel et al (2009) p.84〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「complexity function」の詳細全文を読む スポンサード リンク
|